Present day semiconductor chips can have tens of millions of individual wires. Sophisticated routing software programs are used to automatically route these wires. However, owing to the sheer number of wires and the complexity of the wiring, a considerable amount of time may be expended even though the routing process is automated (e.g., 24 hours or more).
Parallel processing techniques such as multi-threading have been attempted in order to reduce the routing time. The term “thread” is often used to refer to a sequential stream of program code instructions and/or the processing resources used to process such a stream. Multi-threading is the concurrent execution of more than one thread. For instance, if a computing system has two single threaded CPUs, the computing system can be configured as a multi-threaded machine that concurrently executes two separate threads.
In order to enhance the processing performance of a multi-threaded machine, threads should be able to perform their respective tasks without being dependent on one another. Said another way, each thread should be able to execute in isolation of the other thread(s). In the context of semiconductor chip routing, multi-threading can be easily applied to “detail” routing but not “global” routing.
If the surface area of a semiconductor chip is viewed as a grid of smaller surfaces or “tiles”, multi-threaded routing is easily applied to the localized wires within tiles (detail routing) but not to global wires that extend across multiple tiles (global routing). With respect to detail routing, application of one thread to one tile and another thread to another tile corresponds to an environment where the two threads can operate in isolation of one another because the local wires of the first tile can not occupy the same space as the local wires of the second tile.
By contrast, with respect to global routing, many global nets could potentially occupy the same tile(s). As such, there may be interdependence between nets (because they may share the same tile(s)) and/or interdependence between tile(s) (because they may include sections of a same wiring space). These interdependencies impose difficulties when trying to impose an operating environment for multiple concurrent threads that operate in isolation of one another.